package Sep.PaiLie;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


// 47. 全排列 II
class Pao{
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] a = {1,1,2};
        s.permuteUnique(a);
    }
}

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> tmp = new ArrayList<>();
        Arrays.sort(nums);
        boolean[] vis = new boolean[nums.length];
        Arrays.fill(vis, false);
        search(nums, 0, tmp, ans,vis);
        return ans;
    }

    /**
     * 回溯
     * 每次循环枚举第start位,相同元素只有第一个可以放在这一位
     */
    public void search(int[] nums,int start,List<Integer> tmp,List<List<Integer>> ans,boolean[] vis){
        if(start==nums.length){
            ans.add(new ArrayList<>(tmp));
            return;
        }
        for(int i=0;i<nums.length;i++){
            //判断能不能被用,以及是不是可以放在本位
            if(vis[i]||(i>0&&nums[i]==nums[i-1]&&!vis[i-1])){
                continue;
            }
            tmp.add(nums[i]);
            vis[i]=true;
            search(nums, start+1, tmp, ans, vis);
            tmp.remove(start);
            vis[i]= false;
        }
    }
}